Grokking LinkedIn Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
LinkedIn Easy
Find Pivot Index (easy)
Solution: Find Pivot Index
Isomorphic Strings (easy)
Solution: Isomorphic Strings
Second Minimum Node In a Binary Tree (easy)
Solution: Second Minimum Node In a Binary Tree
Minimum Time to Type Word Using Special Typewriter (easy)
Solution: Minimum Time to Type Word Using Special Typewriter
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Can Place Flowers (easy)
Solution: Can Place Flowers
Valid Perfect Square (easy)
Solution: Valid Perfect Square
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Sqrt (easy)
Solution: Sqrt
Valid Palindrome (easy)
Solution: Valid Palindrome
LinkedIn Medium
Rotate List (medium)
Solution: Rotate List
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Valid Triangle Number (medium)
Solution: Valid Triangle Number
Valid Parenthesis String (medium)
Solution: Valid Parenthesis String
Edit Distance (medium)
Solution: Edit Distance
Remove All Ones With Row and Column Flips II (medium)
Solution: Remove All Ones With Row and Column Flips II
Reverse Integer (medium)
Solution: Reverse Integer
Triplet Sum to Zero (medium)
Solution: Triplet Sum to Zero
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Decode Ways (medium)
Solution: Decode Ways
Quadruple Sum to Target (medium)
Solution: Quadruple Sum to Target
Next Permutation (medium)
Solution: Next Permutation
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Word Search (medium)
Solution: Word Search
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
House Robber II (medium)
Solution: House Robber II
Coin Change
Solution: Coin Change
Design Add and Search Words Data Structure (medium)
Solution: Design Add and Search Words Data Structure
Merge Intervals (medium)
Solution: Merge Intervals
Number of Islands (easy)
Solution: Number of Islands
Longest Palindromic Subsequence (medium)
Solution: Longest Palindromic Subsequence
Kth Smallest Number (medium)
Solution: Kth Smallest Number
Maximum Product Subarray (medium)
Solution: Maximum Product Subarray
Same Tree (medium)
Solution: Same Tree
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: Decode Ways

Problem Statement

You have given a string that consists only of digits. This string can be decoded into a set of alphabets where '1' can be represented as 'A', '2' as 'B', ... , '26' as 'Z'. The task is to determine how many ways the given digit string can be decoded into alphabets.

Examples

    • Input: "121"
    • Expected Output: 3
    • Justification: The string "121" can be decoded as "ABA", "AU", and "LA".
    • Input: "27"
    • Expected Output: 1
    • Justification: The string "27" can only be decoded as "BG".
    • Input: "110"
    • Expected Output: 1
    • Justification: The string "110" can only be decoded as "JA".

Constraints:

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).

Solution

Our approach to solving this problem involves using dynamic programming to iteratively build the solution. Given a string of digits, we want to determine how many ways it can be decoded into alphabets. The key insight is that the number of ways to decode a string of length i is dependent on the number of ways to decode the previous two substrings of length i-1 and i-2. We'll use two variables, prev and current, to store these values and update them as we loop through the string.

  1. Initialization: Begin by checking if the string is valid for decoding (e.g., it should not start with a '0'). If the string is invalid, return 0. Next, initialize two variables, prev and current, both set to 1. prev will store the number of ways to decode the string of length i-2, and current will store the number of ways to decode the string of length i-1.

  2. Iterate Through the String: Loop through the string from the second character to the end. For each character, compute the number of ways it can be decoded when combined with the previous character.

  3. Update Variables: For each character, evaluate the following conditions:

    • If the current character and the previous character form a valid number between 10 and 26, they can be decoded together.
    • If the current character is not '0', it can be decoded individually. Use these conditions to update the prev and current variables accordingly.
  4. Return the Result: Once the iteration completes, the current variable will hold the total number of ways the entire string can be decoded. Return this value.

This dynamic programming approach is efficient because it computes the solution by using previously calculated results, and it avoids redundant calculations. By tracking and updating the number of ways to decode the current and previous substrings, the algorithm effectively builds the solution for the entire string.

Algorithm Walkthrough

Consider the input "121":

  • Initialize prev = 1 and current = 1.
  • For the second character '2':
    • "12" can be decoded as "AB" or "L".
    • Update prev and current by swapping their values and setting current += prev.
    • Now, prev = 1 and current = 2.
  • For the third character '1':
    • "21" can be decoded as "BA" or "U".
    • Again, update prev and current.
    • Now, prev = 2 and current = 3.
  • The final answer is 3, which is the value of current.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: O(N), where N is the length of the string. We loop through the string once.

  • Space Complexity: O(1), as we only use a constant amount of space regardless of the input size.

Decode Ways (medium)
Quadruple Sum to Target (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Algorithm Walkthrough

Code

Complexity Analysis